#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<stack>
#include<list>
#include<queue>
#include<mpi.h>
#include<vector>
#include<set>
#include<time.h>
#define CACHE_SET 256
#define CACHE_WAY 4
#define MUSK 0xff
#define GROUP_SIZE 10
#define random
int main(int argc, char** argv){
  	int np;
  	int rank;
	int ns;
	int ranks;
  	MPI_Status status;
	FILE * inf;
	FILE * outf;
	long long v,e;
	long long** con;
	long long* icon;
	double* cb;
	long long lc;
	long long lcbuf;
	long long lcsbuf[2];
	double* cbb;
	long long*** cache;
	long long** tag;
	long long** csize;
	#ifndef random
	unsigned int** lru;
	#endif
	long long hit=0;
	long long miss=0;

  // MPI init
  MPI_Init(&argc, &argv);
  MPI_Comm_size(MPI_COMM_WORLD, &np);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	srand(time(NULL));
	ns=np/2;
	if(rank==0){
		lc=ns;
	}
	if(rank>=ns){
		ranks=rank-ns;
	}else{
		ranks=rank;
	}
	//printf("rank %d ranks %d \n",rank,ranks);
  // TODO: WTF!
  //argv = & argv[2];

	inf=fopen(argv[1],"r");

	if(rank==0){
		outf=fopen(argv[2],"w");
	}
	
	fscanf(inf,"%lld %lld\n",&v,&e);
	printf("%lld %lld rank %d\n",v,e,rank);

	//LD
	if(rank>=ns){
		con =new long long*[(v/ns)+1];
		icon=new long long[(v/ns)+1];
		std::vector<long long> connection[(v/ns)+1];

		for(long long i=0;i<e;i++){
			long long v1,v2;
			fscanf(inf,"%lld %lld\n",&v1,&v2);
			if(v1%ns==ranks){
				connection[v1/ns].push_back(v2);
			}
			if(v2%ns==ranks){
				connection[v2/ns].push_back(v1);
			}
		}

		for(long long i=0;i<(v/ns)+1;i++){
			if(connection[i].size()==0){
				continue;
			}
			con[i]=new long long[connection[i].size()];
			icon[i]=connection[i].size();
			for(long long j=0;j<connection[i].size();j++){
				con[i][j]=connection[i][j];
			}
			connection[i].clear();
		}
	}

  std::set<long long> *my_nodes, *their_nodes;
	//Init cache
	if(rank<ns){
    // get list of nodes to work on
    unsigned int done = 0;
    unsigned int cur_rank = 0;
    std::set<long long>* mine, *theirs;
    long long src, dst, node_count = 0;

    my_nodes = new std::set<long long>;
    their_nodes = new std::set<long long>;

    while(!done) {
      if (rank == cur_rank) {
        mine = my_nodes;
        theirs = their_nodes;
      }
      else {
        mine = their_nodes;
        theirs = my_nodes;
      }

      for(unsigned int i=0; i<GROUP_SIZE;) {
        fscanf(inf, "%lld\t%lld", &src, &dst);
        if (theirs->find(src) == theirs->end() && mine->find(src) == mine->end()) {
          i++;
          node_count++;
          mine->insert(src);
        }
        if (theirs->find(dst) == theirs->end() && mine->find(dst) == mine->end()) {
          i++;
          node_count++;
          mine->insert(dst);
        }
        if (node_count == v) {
          done = 1;
        }
      }
      cur_rank =(cur_rank+1)%(ns);
    }
    free(their_nodes);

		cache= new long long**[CACHE_SET];//# of vertex in cache;
		tag=new long long*[CACHE_SET];// cache tag, -1 for invalid
		csize=new long long*[CACHE_SET];
		#ifndef random
		lru=new unsigned int*[CACHE_SET];
		#endif
		for(int i=0;i<CACHE_SET;i++){
			cache[i]=new long long*[CACHE_WAY];
			tag[i]=new long long[CACHE_WAY];
			csize[i]=new long long[CACHE_WAY];
			#ifndef random
			lru[i]=new unsigned int[CACHE_WAY];
			#endif
			for(int j=0;j<CACHE_WAY;j++){
				cache[i][j]=new long long[1];
				tag[i][j]=-1;
				csize[i][j]=0;
				#ifndef random
				lru[i][j]=j;
				#endif	
			}
		}
	}

  fclose(inf);
	MPI_Barrier(MPI_COMM_WORLD);	

	if(rank<ns){
		//comp node
		//printf("comp rank %d\n",rank);
		cb=new double[v];
		for(long long i=0;i<v;i++){
			cb[i]=0;
		}
		std::stack<long long> st;
		std::list<long long> p[v];
		long long th[v];
		long long d[v];
		std::queue<long long> q;
		double sgm[v];
		long long w;
		long long vi;
		long long csbuf[2];
		long long crbuf[v];
		int crc;
		int way;

		//for(long long s=rank;s<v;s+=ns){
    for(std::set<long long>::iterator it = my_nodes->begin(); it != my_nodes->end(); it++) {
      long long s = *it;
			if(hit+miss!=0){
				printf("comp rank %d start src %lld hit rate: %lf hit %lld miss %lld\n",rank,s,((double)(hit)/(double)(hit+miss)),hit,miss);
			}else{
				printf("comp rank %d start src %lld\n",rank,s);
			}
			while(!st.empty()){
				st.pop();
			}
			for(long long i=0;i<v;i++){
				p[i].clear();
				if(i==s){
					th[i]=1;
					d[i]=0;
				}else{
					th[i]=0;
					d[i]=-1;
				}

			}
			while(!q.empty()){
		                q.pop();
		        }
			q.push(s);
			while(!q.empty()){
				vi=q.front();
				st.push(vi);
				q.pop();
				//First try cache then remote
				way=-1;
				for(int i=0;i<CACHE_WAY;i++){
					if(tag[vi&MUSK][i]==vi){
						way=i;
						break;
					}
				}
				if(way!=-1){//hit
					//printf("##!!##Hit! rank %d v %lld\n",rank,vi);
					hit++;
					//do lru
					#ifndef random
					for(int j=0;j<CACHE_WAY;j++){
						if(lru[vi&MUSK][j]<lru[vi&MUSK][way]){
							lru[vi&MUSK][j]++;
						}
					}
					lru[vi&MUSK][way]=0;
					#endif
					//compute
					for(long long i=0;i<csize[vi&MUSK][way];i++){
						if(d[cache[vi&MUSK][way][i]]<0){
							q.push(cache[vi&MUSK][way][i]);
							d[cache[vi&MUSK][way][i]]=d[vi]+1;
						}
						if(d[cache[vi&MUSK][way][i]]==d[vi]+1){
							th[cache[vi&MUSK][way][i]]+=th[vi];
							p[cache[vi&MUSK][way][i]].push_back(vi);
						}
					}
				}else{//miss
					miss++;
					csbuf[0]=rank;
					csbuf[1]=vi;
					//printf("comp rank %d start src %lld request %lld\n",rank,s,vi);
					MPI_Send(&csbuf[0], 2, MPI_LONG_LONG, ns+(vi%ns), 0, MPI_COMM_WORLD);
					MPI_Recv(&crbuf[0], v, MPI_LONG_LONG, ns+(vi%ns), 0, MPI_COMM_WORLD, &status);
					MPI_Get_count(&status, MPI_LONG_LONG, &crc);
					//printf("comp rank %d start src %lld request %lld get %d\n",rank,s,vi,crc);
					//get victim
					#ifdef random
					way=rand()%CACHE_WAY;
					#endif
					#ifndef random
					for(int j=0;j<CACHE_WAY;j++){
						if(lru[vi&MUSK][j]==CACHE_WAY-1){
							way=j;
							break;
						}
					}
					#endif	
					//do lru
					#ifndef random
					for(int j=0;j<CACHE_WAY;j++){
						lru[vi&MUSK][j]++;
					}
					lru[vi&MUSK][way]=0;
					#endif					
					tag[vi&MUSK][way]=vi;
					csize[vi&MUSK][way]=crc;
					delete[] cache[vi&MUSK][way];
					cache[vi&MUSK][way]=new long long[crc];
					for(long long i=0;i<crc;i++){
						cache[vi&MUSK][way][i]=crbuf[i];//update cache
						if(d[crbuf[i]]<0){
							q.push(crbuf[i]);
							d[crbuf[i]]=d[vi]+1;
						}
						if(d[crbuf[i]]==d[vi]+1){
							th[crbuf[i]]+=th[vi];
							p[crbuf[i]].push_back(vi);
						}
					}
				}
			}
			for(long long i=0;i<v;i++){
				sgm[i]=0;
			}
			while(!st.empty()){
				w=st.top();
				st.pop();
				for(std::list<long long>::iterator it=p[w].begin();it!=p[w].end(); ++it){
					sgm[*it]+=((th[*it]+0.0)/(th[w]+0.0))*(1+sgm[w]);
				}
				if(w!=s){
					cb[w]+=sgm[w];
				}
			}
		}
		//printf("comp end rank %d\n",rank);
		if(rank==0){
			lc--;
		}else{
			MPI_Send(&rank, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
		}
		if(rank==0){
			for(int i=0;i<ns-1;i++){
				MPI_Recv(&lcbuf, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
				lc--;
			}
			lcsbuf[0]=0;
			lcsbuf[1]=-1;
			for(int i=0;i<=ns-1;i++){
				MPI_Send(&lcsbuf[0], 2, MPI_LONG_LONG, ns+i, 0, MPI_COMM_WORLD);
			}
		}
	}else{
		//sto node
		//printf("sto rank %d\n",rank);
		long long srbuf[2];// comp node, request v-->k (-1 means end)
		long long ssbuf[v];
		long long k;
		//pthread_mutex_t bp;
		while(1){
			//pthread_mutex_lock(&bp);
			MPI_Recv(&srbuf[0], 2, MPI_LONG_LONG, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
			//printf("sto rank %d recv req %lld from %lld\n",rank, srbuf[1], srbuf[0]);
///*
			if(srbuf[1]<0){
				break;
			}
			k=srbuf[1]/ns;
			for(long long i=0;i<icon[k]; i++){
				ssbuf[i]=con[k][i];
			}
//*/
			//printf("sto rank %d recv req %lld from %lld send %lld\n",rank, srbuf[1], srbuf[0], icon[k]);
			MPI_Send(&ssbuf[0], icon[k], MPI_LONG_LONG,(int)(srbuf[0]), 0, MPI_COMM_WORLD);
			//pthread_mutex_unlock(&bp);
		}
	}
	MPI_Barrier(MPI_COMM_WORLD);
	if(rank==0){
		cbb=new double[v];
		for(int i=0;i<ns-1;i++){
			MPI_Recv(&cbb[0], v, MPI_DOUBLE, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
			for(long long k=0;k<v;k++){
				cb[k]+=cbb[k];
			}
		}
	}else{
		if(rank<ns){
			MPI_Send(&cb[0], v, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
		}
	}
	MPI_Barrier(MPI_COMM_WORLD);
	if(rank==0){
		for(long long i=0;i<v;i++){
			fprintf(outf,"%lld %lf\n",i,cb[i]);
		}
		fclose(outf);
	}
	MPI_Barrier(MPI_COMM_WORLD);
  	MPI_Finalize();
	return 0;
}
